import java.io.IOException;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		long startTime;
		long endTime;
		/* This first puzzle is easy to solve.
		   1 4 2
		   3   5
		   6 7 8 */
//		int[] puzzle = {1, 4, 2, 3, 0, 5, 6, 7, 8};

		/* Custom puzzle - This puzzle should take about 6
		 * 
		 */
//		int[] puzzle = {1, 4, 2, 6, 3, 5, 7, 8, 0};
		
		/* This second puzzle is more difficult.
		   2 6 7
		     5 1
		   8 3 4 */
//		int[] puzzle = {2, 6, 7, 0, 5, 1, 8, 3, 4};

		/* This third puzzle (from the textbook) is even harder.
		   7 2 4
		   5   6
		   8 3 1 */
//		int[] puzzle = {7, 2, 4, 5, 0, 6, 8, 3, 1};

		/* This forth puzzle is the most difficult yet, but the solution sequence
		   follows a simple pattern.
		   8 7 6
		   5 4 3
		   2 1   */
//		int[] puzzle = {8, 7, 6, 5, 4, 3, 2, 1, 0};
		
		/* This fifth puzzle one of the two puzzles with the longest solution
		   sequence.
		   8 7 6
		     4 1
		   2 5 3 */
		int[] puzzle = {8, 7, 6, 0, 4, 1, 2, 5, 3};

		int[] end = {0, 1, 2, 3, 4, 5, 6, 7, 8};
/*
		CityDB db = new CityDB();
		StateWithHeuristic start = db.get("Seattle, WA");
		StateWithHeuristic goal = db.get("Austin, TX");
		List<StateWithCost> results = AStarSearch.solve(start, goal);
//		List<StateWithCost> results = GreedyBestFirstSearch.solve(start, goal);
*/

		SlidingPuzzle start = new SlidingPuzzle(puzzle);
		SlidingPuzzle goal = new SlidingPuzzle(end);

//		startTime = System.currentTimeMillis();		
//		List<StateWithCost> results = GreedyBestFirstSearch.solve(start, goal);
//		endTime = System.currentTimeMillis();
		
		startTime = System.currentTimeMillis();
		List<StateWithCost> results = AStarSearch.solve(start, goal);
		endTime = System.currentTimeMillis();
		
		System.out.println("\nSolution in " + (results.size()-1) + " moves in " +
		(endTime-startTime + " ms"));
		for(StateWithCost result:results)
		{
			System.out.println(result);
		}
		
	}
}